package com.hjx.leetcode;

/**
 * 907. 子数组的最小值之和
 *
 * 给定一个整数数组 A，找到 min(B) 的总和，其中 B 的范围为 A 的每个（连续）子数组。
 *
 * 由于答案可能很大，因此返回答案模 10^9 + 7。
 *
 *
 *
 * 示例：
 *
 * 输入：[3,1,2,4]
 * 输出：17
 * 解释：
 * 子数组为 [3]，[1]，[2]，[4]，[3,1]，[1,2]，[2,4]，[3,1,2]，[1,2,4]，[3,1,2,4]。
 * 最小值为 3，1，2，4，1，1，2，1，1，1，和为 17。
 *
 *
 * 提示：
 *
 * 1 <= A <= 30000
 * 1 <= A[i] <= 30000
 */
public class LeetCode_907 {

    /**
     * 第二版 记忆化结果
     *
     * @param A
     * @return
     */
    public int sumSubarrayMins(int[] A) {
        int minSumTotal= 0;
        int[][] dp = new int[A.length][A.length];

        //不同子元素规模数，即 1个元素的子元素 2个元素 ... n个元素
        for (int i = 1; i <= A.length; i++) {
            //每种规模的子元素，最小值和
            int minSum = 0;
            System.out.print("子数组元素个数等于" + (i) + "| ");
            //从n项中挑选j项， n = A.length + 1 - i
            for (int j = 0; j <= A.length - i; j++){

                int min;
                if (i==1){
                    min = A[j];
                    dp[i-1][j] = A[j];
                } else {
                    //A的下标不光取决于i 还要取决以j
                    min = Math.min(dp[i-2][j], A[i-1+j]);
                    dp[i-1][j] = min;
                }
                System.out.print(min + "| ");
                //累加最小值
                minSum+=min;

            }
            minSumTotal += minSum;
            System.out.println("最小值和" + minSum);

        }
        return minSumTotal;
    }


    /**
     * 第一版 未对每种子元素集合做记忆化 O(N^3)
     *
     * @param A
     * @return
     */
    public int sumSubarrayMins1(int[] A) {
        int minSumTotal= 0;

        //不同子元素规模数，即 1个元素的子元素 2个元素 ... n个元素
        for (int i = 1; i <= A.length; i++) {
            //每种规模的子元素，最小值和
            int minSum = 0;
            //从n项中挑选j项， n = A.length + 1 - i
            for (int j = 0; j < A.length+1-i; j++){
                int min = Integer.MAX_VALUE;

                //比较挑选出的项的最小值
                for (int k = j; k< i+j; k++){
                    System.out.print(A[k] + " ");
                    if (A[k] < min){
                        min = A[k];
                    }
                }
                System.out.print("|");
                //累加最小值
                minSum+=min;

            }
            minSumTotal += minSum;
            System.out.println("最小值" + minSum);

        }
        return minSumTotal;
    }

}
